package lc.q201_250;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
 *
 * 生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。
 */
public class Q241 {

    public static void main(String[] args) {
        Q241 q241 = new Q241();
        System.out.println(q241.diffWaysToCompute("2*3-4*5"));
    }

    public List<Integer> diffWaysToCompute(String expression) {
        // 本质等于有多少出入栈方式,排列组合问题
        List<Integer> ops = new ArrayList<>();
        int num = 0;
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*' ) {
                ops.add(num);
                num = 0;
                switch (c) {
                    case '+':
                        ops.add(-1);
                        break;
                    case '-':
                        ops.add(-2);
                        break;
                    case '*':
                        ops.add(-3);
                        break;
                }
            } else  {
                num = num * 10 + c - '0';
            }
        }
        ops.add(num);
        // 对于每个符号来说，如果其作为最顶层运算，关联的结果，最后的结果就是所有的算子作为顶级运算的结果组合
        // 然后此时，左边右边拆成了两个递归子问题
        // 使用一个dp，dp[i][j]是从第i个数到第j个数计算的所有运算结果
        List<Integer>[][] dp = new List[ops.size()][ops.size()];
        for (int i = 0; i < ops.size(); i++) {
            for (int j = 0; j < ops.size(); j++) {
                dp[i][j] = new ArrayList<Integer>();
            }
        }

        return dfs(dp, 0, ops.size() - 1, ops);

    }

    public List<Integer> dfs(List<Integer>[][] dp, int l, int r, List<Integer> opes) {
        if (dp[l][r].isEmpty()) {
            if (l == r) {
                dp[l][r].add(opes.get(l));
            } else {
                for (int i = l; i < r; i+=2) {
                    List<Integer> left = dfs(dp, l, i, opes);
                    List<Integer> right = dfs(dp, i + 2, r, opes);
                    for (Integer lInt : left) {
                        for (Integer rInt : right) {
                            if (opes.get(i + 1) == -1) {
                                // 加起来
                                dp[l][r].add(lInt + rInt);
                            } else if (opes.get(i + 1) == -2) {
                                dp[l][r].add(lInt - rInt);
                            } else if (opes.get(i + 1) == -3) {
                                dp[l][r].add(lInt * rInt);
                            }
                        }
                    }
                }
            }
        }
        return dp[l][r];
    }
}
